KM-52. 携带研究材料

代码随想录-完全背包的二维版本

完全背包的一维版本

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品都能使用无数次，求解将物品装入背包里物品价值总和最大是多少。

例如：

背包最大重量为 4。

此时放入 4 个物品 0 的价值最大。

分析

自己的想法

我一开始的想法是，因为一个物品可以放入无限次，因此，当我们确定可以放入某个物品的时候，我们就把可放入的所有次数全都遍历一遍，保留最大值即可，因此我们需要在 KM-46. 携带研究材料 的基础上，我们需要添加一层循环，循环变量 k 为放入物品 i 的个数，k 的范围是 [0, j/weight[i]]，然后更新 dp[j] 的值为其最大值。这个方法是可行的，也通过了测试。

但是不够优雅和简洁。多了一层循环，效率也不高。

二维 dp

完全背包和 01 背包问题唯一不同的地方就是同一个物品可以放入背包无限次。或者说每种物品有无限件。

首先我们根据题意来定义 dp 数组：dp[i][j] 表示，用物品 0 到物品 i 这些物品去填充一个容量为 j 的背包，每一个物品可放入无限次的时候，能放入的物品的最大价值。

推到状态转移方程，首先我们要明确有哪些方向可以推导出 dp[i][j]。，分两种情况，背包中的物品包不包含物品 i。

• 不包含物品 i，那说明其实就是 dp[i-1][j] ，dp[i][j] = dp[i-1][j];
• 包含物品 i，那就说明物品组合中至少存在一个物品 i，那么就肯定可以通过在 dp[i][j-weight[i]] 的基础上放入一个物品 i 来达到 dp[i][j] 的条件，因此 dp[i][j]=dp[i][j-weight[i]]+value[i];
  • 注意跟 01 背包的区别，在 01 背包中（KM-46. 携带研究材料）当背包中的物品包含物品 i 的时候，之前的物品最大值是 dp[i-1][j-weight[i]]，为什么，因为在 01 背包中，物品 i 只能放入一次，最后一次放入了物品 i，之前就不能放入物品 i，所以之前的物品的最大值是 dp[i-1][j-weight[i]]，而在完全背包中，物品 i 是可以放入无限个的，最后一次放入物品 i，之前也可能放入物品 i，因此，之前的物品的最大值是 dp[i][j-weight[i]]，这是 01 背包跟完全背包在状态转移方程上的唯一区别。
    最终，dp[i][j] 为这两种情况的最大值：dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);

初始化，根据状态转移方程的依赖关系，我们需要初始化 dp[0][j] 和 dp[i][0]

• dp[0][j]，因为物品 0 可以放入多次，因此只要 j 大于等于物品 0 重量的整数倍，就可以放入这个倍数的物品 0 的值， 因此可以让 j 从 0 开始 dp[0][j] = (j/weight[0])*value[0]; 或者你也可以让 j 从 weight[0] 开始 dp[0][j] = dp[0][j-weight[0]]+value[0];
• dp[i][0]，背包容量为 0，因此可放入的物品的价值全都为 0。

遍历方式，外层遍历物品，从 1 开始，内层遍历容量，从 0 开始，

• 如果 j 小于 weight[i]，直接 dp[i][j] = dp[i-1][j];
• 如果 j 大于 weight[i]``dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);

一维 dp

首先定义 dp 数组 dp[j] 表示容量为 j 的背包所容纳物品的最大值。

然后我们来看状态转移方程，我们可以直接从二维 dp 数组来降维，二维 dp 数组的状态转移方程为 dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);，那么如何降为一维呢？

我们在 KM-46. 携带研究材料 中专门讲解过，为什么一维 dp 的版本中，内层 for 循环遍历背包容量的时候一定要从右往左遍历，因为从左往右遍历的时候，当遍历右侧的容量的时候，左侧的 dp[j] 实际上已经被更新为 dp[i][j]，而不是 dp[i-1][j]，而这恰恰是完全背包问题所需要的，

黄格子为 dp[i-1] 的数据，白格子为 dp[i] 的数据，

因为 j-weight[i] < j， 所以当我们从左往右更新 dp[j] 且马上要更新索引 dp[j] 的时候，dp[j-weight[i]] 已经更新过了， 实际上对应二维 dp 中的，dp[i][j-weight[i]]，但是 dp[j] 还没更新，所以 dp[j] 依然是 dp[i-1][j]。而这刚好对应二维 dp 中的 dp[i][j] 以来的两个 dp 值。

因此，配合 dp[j] 从左往右遍历的顺序，状态转移方程为 dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i])。

然后在一维 dp 数组中，我们是从 i=0 的时候开始遍历，所以我们实际上是在没有选择任何物品的场景下初始化 dp 数组，此时没有任何物品，背包中物品的价值始终是 0。或者也不用初始化，因为 dp 数组默认为 int 数组，所有元素默认为 0。

遍历方式，重点：外层 for 循环遍历物品，内层 for 循环遍历背包容量，且必须从小到大遍历。原因上面介绍过了。

解题

我自己想出来的版本，不够优雅简洁。

public int packageFull(int[] weight, int[] value, int w) {
	int[] dp = new int[w + 1];  
	// 默认初始化为 0 即可  
	dp[0] = 0;  
	for (int i = 0; i < weight.length; ++i) {  
	    for (int j = w; j >= weight[i]; j--) {  
	        // 物品 i 的个数  
	        for (int k = 0; k <= j/weight[i]; k++) {  
	            // 遍历逐步增加物品 i 的过程  
	            // 因为都是更新的一个位置 dp[j] 所以不会有问题  
	            dp[j] = Math.max(dp[j], dp[j - k*weight[i]] + k*value[i]);  
	        }  
	    }  
	}
    return dp[w];
}

优雅解法

二维 dp 数组

public int packageFull(int[] weight, int[] value, int w) {

    int[][] dp = new int[weight.length][w + 1];  

    for(int j=weight[0];j<=w;j++){
        dp[0][j] = dp[0][j-weight[0]]+value[0];
    }

    for(int i=0;i<weight.length;i++){
       dp[i][0] = 0;
    }

    for (int i = 1; i < weight.length; ++i) {  
        for (int j = 0; j <= w; j++) {
            if(j>=weight[0]){
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j - weight[i]] + value[i]);  
            }else{
                dp[i][j] = dp[i-1][j];  
            }  
        }  
    }
    return dp[w];

}

一维 dp 数组

public int packageFull(int[] weight, int[] value, int w) {
	int[] dp = new int[w + 1];  
	// 默认初始化为 0 即可  
	dp[0] = 0;  
	for (int i = 0; i < weight.length; ++i) {  
	    for (int j = weight[i]; j < w + 1; j++) {  
	        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);  
	    }  
	}
    return dp[w];
}

卡码网题解

二维 dp 数组

import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        int space = sc.nextInt();
        int[] weight = new int[length];
        int[] value = new int[length];
        for(int i=0;i<length;i++){
            int w = sc.nextInt();
            int v = sc.nextInt();
            weight[i] = w;
            value[i] = v;
        }

        int[][] dp = new int[length][space+1];

        for(int j=weight[0];j<=space;j++){
            dp[0][j] = dp[0][j-weight[0]]+value[0];
        }
  

        for(int i=0;i<length;i++){
            dp[i][0] = 0;
        }

        for(int i=1;i<length;i++){
            for(int j=0;j<=space;j++){
                if(j>=weight[i]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        System.out.println(dp[length-1][space]);
    }
  

}

一维 dp 数组

import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int length = sc.nextInt();
        int space = sc.nextInt();
        int[] weight = new int[length];
        int[] value = new int[length];
        for(int i=0;i<length;i++){
            int w = sc.nextInt();
            int v = sc.nextInt();
            weight[i] = w;
            value[i] = v;
        }

        int[] dp = new int[space+1];
        for(int i=0;i<length;i++){
            for(int j=weight[i];j<=space;j++){
                // j-weight[i] < j 所以 当dp数组遍历到j的时候 dp[j-weight[i]] 实际上是，dp[i][j-weight[i]]，但是 dp[j] 还没更新，所以 dp[j] 依然是 dp[i-1][j]
                dp[j] = Math.max(dp[j],dp[j-weight[i]]+value[i]);
            }
        }

        System.out.println(dp[space]);
    }

}

相关题

KM-46. 携带研究材料